package com.lw.leetcode.linked.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * 1162. 地图分析
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/5 13:45
 */
public class MaxDistance {


    public static void main(String[] args) {
        MaxDistance test = new MaxDistance();

        // 2
        int[][] arr = {{0, 0, 1, 1, 1}, {0, 1, 1, 0, 0}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, {1, 1, 0, 0, 1}};

        int i = test.maxDistance(arr);
        System.out.println(i);

    }


    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int count = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    list.addLast((i << 24) + (j << 16));
                    count++;
                }
            }
        }
        if (count == 0 || count == n * n) {
            return -1;
        }
        int[][] arr = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int max = 0;
        while (!list.isEmpty()) {
            int value = list.pollFirst();
            int x = value >> 24;
            int y = (value >> 16) & 0XFF;
            int c = value & 0XFF;
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || b < 0 || a == n || b == n || grid[a][b] == 1) {
                    continue;
                }
                grid[a][b] = 1;
                list.addLast((a << 24) + (b << 16) + c + 1);
                max = Math.max(max, c + 1);
            }
        }
        return max;
    }

}
